package buckets.strategies;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import buckets.core.BucketsInstance;
import buckets.core.BucketState;

/**
 * This is a general class for all algorithms that haven't any additional information about
 * how to traverse through state space - they are called uninformed or blind algorithms.
 * 
 * @author vasek
 *
 */
public abstract class BlindSearchAlgorithm extends SearchSpaceSupport implements BucketFillingProblemStrategy {

	protected final LinkedList<BucketState> open = new LinkedList<BucketState>();
	protected final List<BucketState> closed = new ArrayList<BucketState>();
		
	/**
	 * Constructor.
	 * 
	 * @param instance to be solved
	 */
	public BlindSearchAlgorithm(final BucketsInstance instance) {
		super(instance);
	}

	@Override
	public final void run() {
		open.add(new BucketState(instance.getOriginalCapacities()));
		BucketState current = removeState();
		statesCounter++;
		
		while (!isTarget(current)) {			
			final List<BucketState> neighbors = expand(current);			
			for (BucketState state : neighbors) {
				if (!closed.contains(state) && !open.contains(state) && !current.equals(state)) {
					addState(state);
					state.setPredecessor(current);
				}				
			}
			
			if (!closed.contains(current)) {
				closed.add(current);
			}
			
			current = removeState();
			statesCounter++;
		}
		
		path = (LinkedList<BucketState>) backtrackToStart(current); 		
		
	}

	@Override
	public List<BucketState> getResultPath() {
		if (path.isEmpty()) {
			run();
		}
		
		return path;
	}
	
	@Override
	public int getNumberOfPassedStates() {
		return statesCounter;
	}
	
	
	/**
	 * Algorithm specific add state to search space.
	 *  
	 * @param state state to be added
	 */
	protected abstract void addState(final BucketState state);
	
	/**
	 * Algorithm specific get next state from search space.
	 * 
	 * @return next state to be traversed
	 */
	protected abstract BucketState removeState();
		
}
